class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ret = nums[0];
        int count = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            if (ret != nums[i])
            {
                --count;
                if (count == 0)
                {
                    ret = nums[i];
                    count = 1;
                }
            }
            else
                ++count;
        }

        return ret;
    }
};



class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();

        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());

    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        int min_p = prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            ret = max(ret, prices[i] - min_p);
            min_p = min(min_p, prices[i]);
        }

        return ret;
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        for (int i = 1; i < prices.size(); ++i)
            if (prices[i] > prices[i - 1])
                ret += prices[i] - prices[i - 1];

        return ret;
    }
};


class Solution {
public:
    bool canJump(vector<int>& nums) {
        int left = 0, right = 0, max_pos = 0;
        while (left <= right)
        {
            if (max_pos >= nums.size() - 1)
                return true;

            for (int i = left; i <= right; ++i)
                max_pos = max(max_pos, i + nums[i]);

            left = right + 1;
            right = max_pos;
        }
        
        return false;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int left = 0, right = 0, max_pos = 0;
        int ret = 0;
        while (left <= right)
        {
            if (max_pos >= nums.size() - 1)
                return ret;

            for (int i = left; i <= right; ++i)
                max_pos = max(max_pos, i + nums[i]);

            left = right + 1;
            right = max_pos;
            ++ret;
        }
        
        return -1;
    }
};